package string.understanding;

import java.util.Stack;

/**
 * @Classname : DecodeString
 * @Description : 394. 字符串解码
 * https://leetcode.cn/problems/decode-string/
 * @Author : cty
 * @Date 2023/4/7 22:47
 */


public class DecodeString {
    public String decodeString(String s) {
        Stack<String> stack = new Stack<>();
        // 遍历字符串
        for (int i = 0; i < s.length(); i++) {
            // 获取数字
            i = getNum(stack, s, i);
            // 若当前字符非右中括号则入栈
            if (s.charAt(i) != ']') {
                stack.push(String.valueOf(s.charAt(i)));
            } else {
                // 获取待重复的字符串
                StringBuilder str = new StringBuilder();
                while(!"[".equals(stack.peek())) str.append(stack.pop());
                // 将左中括号出栈
                stack.pop();
                // 获取字符串重复次数
                int times = Integer.valueOf(stack.pop());
                // 将字符串重复指定次数
                StringBuilder multiStr = new StringBuilder();
                for (int j = 0; j < times; j++) multiStr.append(str);
                // 将重复字符串再入栈
                stack.push(multiStr.toString());
            }
        }
        // 拼接栈中字符串，注意要将字符串逆序
        StringBuilder ans = new StringBuilder();
        while (!stack.isEmpty()) ans.append(stack.pop());
        return ans.reverse().toString();
    }

    // 获取数字并移动下标
    private int getNum(Stack<String> stack, String s, int i) {
        int num = 0;
        while (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
            num = s.charAt(i) - '0' + num * 10;
            i++;
        }
        // 注意数字大于0才入栈
        if (num > 0) {
            stack.push(String.valueOf(num));
        }
        return i;
    }
}
